{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f04dd603-a2d1-48ce-8c17-9f1dba8de1ee",
   "metadata": {},
   "source": [
    "Chapter 04\n",
    "\n",
    "# 伴随矩阵法求解逆矩阵\n",
    "《线性代数》 | 鸢尾花书：数学不难"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccafb456-2453-4c82-8a65-b1963a370cb2",
   "metadata": {},
   "source": [
    "该代码实现了计算矩阵的**行列式（determinant）**的方法，使用的是**Laplace展开（Laplace Expansion）**，即按某一行或某一列展开计算行列式。\n",
    "\n",
    "---\n",
    "\n",
    "### **1. 余子矩阵（Minor Matrix）**\n",
    "给定一个$n \\times n$矩阵 $A$，其某个元素 $A_{ij}$ 的**余子矩阵（minor matrix）** $M_{ij}$ 是删除该元素所在的第 $i$ 行和第 $j$ 列后得到的 $(n-1) \\times (n-1)$ 矩阵。代码中的 `get_minor(matrix, row, col)` 函数通过 `np.delete` 删除指定行和列来获取余子矩阵：\n",
    "\n",
    "$$\n",
    "M_{ij} = \\text{Minor}(A, i, j)\n",
    "$$\n",
    "\n",
    "---\n",
    "\n",
    "### **2. Laplace 展开计算行列式**\n",
    "对于 $n \\times n$ 矩阵 $A$，行列式 $\\det(A)$ 递归地按第一行展开（也可以按任意一行或一列展开，但本代码按第一行展开）：\n",
    "\n",
    "$$\n",
    "\\det(A) = \\sum_{j=0}^{n-1} (-1)^j A_{0j} \\det(M_{0j})\n",
    "$$\n",
    "\n",
    "其中：\n",
    "- $A_{0j}$ 是矩阵 $A$ 第一行的第 $j$ 个元素。\n",
    "- $M_{0j}$ 是 $A_{0j}$ 对应的余子矩阵。\n",
    "- $(-1)^j$ 是交替的符号，用于计算**代数余子式（cofactor）**。\n",
    "\n",
    "代码中 `determinant(matrix)` 递归地调用自己来计算 $\\det(M_{0j})$，最终得到 $\\det(A)$。\n",
    "\n",
    "---\n",
    "\n",
    "### **3. 递归终止条件**\n",
    "在 `determinant(matrix)` 中：\n",
    "- 如果 $n=1$，即 $A$ 仅为 $1 \\times 1$ 矩阵，则 $\\det(A) = A_{00}$。\n",
    "- 如果 $n=2$，即 $A$ 为 $2 \\times 2$ 矩阵，则直接使用公式：\n",
    "\n",
    "$$\n",
    "\\det \\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} = ad - bc\n",
    "$$\n",
    "\n",
    "- 对于 $n \\geq 3$，使用 Laplace 展开进行递归计算。\n",
    "\n",
    "---\n",
    "\n",
    "### **4. 计算示例**\n",
    "给定矩阵：\n",
    "$$\n",
    "A = \\begin{bmatrix} 1 & 2 & 3 \\\\ 3 & 0 & 1 \\\\ 1 & 2 & 1 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "展开计算：\n",
    "1. 按第一行展开：\n",
    "\n",
    "$$\n",
    "\\det(A) = 1 \\cdot \\det \\begin{bmatrix} 0 & 1 \\\\ 2 & 1 \\end{bmatrix} - 2 \\cdot \\det \\begin{bmatrix} 3 & 1 \\\\ 1 & 1 \\end{bmatrix} + 3 \\cdot \\det \\begin{bmatrix} 3 & 0 \\\\ 1 & 2 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "2. 计算 $2 \\times 2$ 子矩阵的行列式：\n",
    "\n",
    "$$\n",
    "\\det \\begin{bmatrix} 0 & 1 \\\\ 2 & 1 \\end{bmatrix} = 0 \\cdot 1 - 1 \\cdot 2 = -2\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\det \\begin{bmatrix} 3 & 1 \\\\ 1 & 1 \\end{bmatrix} = 3 \\cdot 1 - 1 \\cdot 1 = 2\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\det \\begin{bmatrix} 3 & 0 \\\\ 1 & 2 \\end{bmatrix} = 3 \\cdot 2 - 0 \\cdot 1 = 6\n",
    "$$\n",
    "\n",
    "3. 代入计算：\n",
    "\n",
    "$$\n",
    "\\det(A) = 1 \\cdot (-2) - 2 \\cdot (2) + 3 \\cdot (6)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\det(A) = -2 - 4 + 18 = 12\n",
    "$$\n",
    "\n",
    "因此，最终的行列式结果为 **12**。\n",
    "\n",
    "---\n",
    "\n",
    "### **总结**\n",
    "- 代码实现了 **递归计算行列式**，基于 Laplace 展开，选择第一行进行展开计算。\n",
    "- 通过 `get_minor()` 计算余子矩阵，再通过递归调用 `determinant()` 计算行列式。\n",
    "- 终止条件：$1 \\times 1$ 或 $2 \\times 2$ 矩阵直接计算。\n",
    "- 计算复杂度为 $O(n!)$，随着矩阵大小增长，计算量呈指数增长，因此适用于小矩阵。\n",
    "\n",
    "最终，代码计算出矩阵 $A$ 的行列式值为 $12$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47bc7070-fd14-4a88-936f-85385266166e",
   "metadata": {},
   "source": [
    "## 初始化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d7296ce6-de4d-4b77-b55d-e8e601f5e615",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cd29e1b-f98f-4088-b9ec-a50b5a406b4d",
   "metadata": {},
   "source": [
    "## 自定义函数，提取余子矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d29ff57c-b087-49b1-b8d9-fe561c5a4ac1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_minor(A, row_idx, col_idx):\n",
    "    A_ij = np.delete(np.delete(A, row_idx, axis=0), col_idx, axis=1)\n",
    "    # 去掉指定的行、列\n",
    "    return A_ij"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cc8393f-b473-4da4-8a4c-7ddcd17166d7",
   "metadata": {},
   "source": [
    "## 用Laplace展开递归计算行列式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "bcc5a135-f965-4792-9fcd-6f8d1fa68132",
   "metadata": {},
   "outputs": [],
   "source": [
    "def determinant(matrix):\n",
    "\n",
    "    n = matrix.shape[0]\n",
    "    if n == 1:\n",
    "        return matrix[0, 0]\n",
    "    if n == 2:\n",
    "        return matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]\n",
    "    \n",
    "    det = 0\n",
    "    for col_idx in range(n):\n",
    "        minor = cal_minor(matrix, 0, col_idx)  # 沿第一行展开\n",
    "        cofactor = ((-1) ** col_idx) * determinant(minor)  # 计算代数余子式\n",
    "        # 相当于 (-1) ** ((col_idx + 1) + 1) = (-1) ** col_idx\n",
    "        det += matrix[0, col] * cofactor  # 计算行列式\n",
    "    \n",
    "    return det"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9771c69-eb08-4500-8184-fe90ab522720",
   "metadata": {},
   "source": [
    "## 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d49d283-744e-4704-a121-243f5fc6c8c9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[1, 2, 3], \n",
    "              [3, 0, 1], \n",
    "              [1, 2, 1]])\n",
    "A_det = determinant(A)\n",
    "A_det"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "954b7525-dcef-47cb-af13-40c741ca3891",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "070c3389-8048-43a3-baa7-6666009bce96",
   "metadata": {},
   "source": [
    "作者\t**生姜DrGinger**  \n",
    "脚本\t**生姜DrGinger**  \n",
    "视频\t**崔崔CuiCui**  \n",
    "开源资源\t[**GitHub**](https://github.com/Visualize-ML)  \n",
    "平台\t[**油管**](https://www.youtube.com/@DrGinger_Jiang)\t\t\n",
    "\t\t[**iris小课堂**](https://space.bilibili.com/3546865719052873)\t\t\n",
    "\t\t[**生姜DrGinger**](https://space.bilibili.com/513194466)  "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:base] *",
   "language": "python",
   "name": "conda-base-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
